#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    TreeNode* _GetTreeR(vector<int>& nums, int left, int right)
    {
        if (left > right)
            return nullptr;
        int mid = left;
        int max = nums[left];
        for (int i = left; i <= right; i++)
        {
            if (nums[mid] < nums[i])
            {
                mid = i;
                max = nums[i];
            }
        }
        TreeNode* root = new TreeNode(max);
        root->left = _GetTreeR(nums, left, mid - 1);
        root->right = _GetTreeR(nums, mid + 1, right);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return _GetTreeR(nums, 0, nums.size() - 1);
    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2)
    {
        if (root1 == nullptr && root2 == nullptr)
            return nullptr;

        TreeNode* root = nullptr;
        if (root1 && root2)
        {
            root = new TreeNode(root1->val + root2->val);
            root->left = mergeTrees(root1->left, root2->left);
            root->right = mergeTrees(root1->right, root2->right);
        }
        else if (root1)
        {
            root = new TreeNode(root1->val);
            root->left = mergeTrees(root1->left, nullptr);
            root->right = mergeTrees(root1->right, nullptr);
        }
        else
        {
            root = new TreeNode(root2->val);
            root->left = mergeTrees(nullptr, root2->left);
            root->right = mergeTrees(nullptr, root2->right);
        }
        return root;
    }
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr)
            return nullptr;
        if (root->val == val)
            return root;
        else if (root->val > val)
            return searchBST(root->left, val);
        else
            return searchBST(root->right, val);
        return root;
    }
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)
            return true;
        if (root->left)
        {
            TreeNode* tmp = root->left;
            if (tmp->val >= root->val)
                return false;
            while (tmp->right)
            {
                tmp = tmp->right;
                if (tmp->val >= root->val)
                    return false;
            }
        }
        if (root->right)
        {
            TreeNode* tmp = root->right;
            if (tmp->val <= root->val)
                return false;
            while (tmp->left)
            {
                tmp = tmp->left;
                if (tmp->val <= root->val)
                    return false;
            }
        }
        return isValidBST(root->left) && isValidBST(root->right);
    }
};